SYLLABUS

• 1. Introduction

  • Lesson 1. Analysis of Algorithm.
    ○ Background analysis through a Program and its functions.
  • Lesson 2. Order of Growth.
    ○ A mathematical explanation of the growth analysis through limits and functions.
    ○ A direct way of calculating the order of growth
  • Lesson 3. Asymptotic Notations.
    ○ Best, Average and Worst case explanation through a program.
  • Lesson 4. Big O Notation.
    ○ Graphical and mathematical explanation.
    ○ Calculation
    ○ Applications at Linear Search
  • Lesson 5. Omega Notation.
    ○ Graphical and mathematical explanation.
    ○ Calculation.
  • Lesson 6. Theta Notation.
    ○ Graphical and mathematical explanation.
    ○ Calculation.
  • Lesson 7. Analysis of common loops.
    ○ Single, multiple and nested loops
  • Lesson 8. Analysis of Recursion.
    ○ Various calculations through Recursion Tree method
  • Lesson 9. Space Complexity.
    ○ Basic Programs
    ○ Auxiliary Space
    ○ Space Analysis of Recursion
    ○ Space Analysis of Fibonacci number

• 2. Mathematics

  • Lesson 1. Mathematics
    ○ Count Digits
    ○ Palindrome Numbers
    ○ Factorial of Numbers
    ○ GCD of Two Numbers
    ○ LCM of Two Numbers
    ○ Check for Prime
    ○ Prime Factors
    ○ Sieve of Eratosthenes
    ○ Computing Power

• 3. Bit Magic

  • Lesson 1. Bitwise Operators in C++.
    ○ Operation of AND, OR, XOR operators.
    ○ Operation of Left Shift, Right Shift and Bitwise Not.
  • Lesson 2. Bitwise Operators in Java.
    ○ Operation of AND, OR.
    ○ Operation of Bitwise Not, Left Shift
    ○ Operation of Right Shift and unsigned Right Shift

• 4. Recursion

  • Lesson 1. Introduction to Recursion.
  • Lesson 2. Applications of Recursion
  • Lesson 3. Writing base cases in Recursion.
    ○ Factorial
    ○ N-th Fibonacci number
  • Lesson 4. Various problems on Recursion.

5. Arrays

• Lesson 1. Introduction and Advantages.
• Lesson 2. Types of Arrays.
  ○ Fixed-sized array
  ○ Dynamic-sized array
• Lesson 3. Operations on Arrays.
  ○ Searching
  ○ Insertions
  ○ Deletion
  ○ Arrays vs other DS
  ○ Reversing - Explanation with complexity
• Lesson 4. Problems.
  ○ Left Rotation of the array by 1
  ○ Check if Sorted
  ○ Left Rotation of the array by D places
  ○ Leaders in an Array
  ○ Maximum Difference Problem
  ○ Frequencies in Sorted Array
  ○ Stock Buy and Sell Problem
  ○ Trapping Rainwater Problem
  ○ Maximum Consecutive 1s
  ○ Maximum Subarray Sum
  ○ Longest Even-Odd Subarray
  ○ Maximum Circular sum subarray
  ○ Majority Element
  ○ Minimum Consecutive Flips
  ○ Sliding Window Technique
  ○ Prefix Sum Technique

• 6. Searching

  • Lesson 1. Binary Search Iterative and Recursive.
  • Lesson 2. Binary Search and various associated problems.
    ○ Index of First Occurence in Sorted Array
    ○ Index of Last Occurence in Sorted Array
    ○ Count of occurrences of x in sorted element
    ○ Count of 1s in a binary sorted array
    ○ Find an element in sorted and rotated array
    ○ Peak element
    ○ Find an element in an infinite sized sorted array
    ○ The square root of an integer
  • Lesson 3. Two Pointer Approach Problems.
    ○ Find pair in an unsorted array which gives sum X
    ○ Find pair in a sorted array which gives sum X
    ○ Find triplet in an array which gives sum X
  • Lesson 4. Problems.
    ○ Median of two sorted arrays
    ○ Majority Element

• 7. Sorting

  • Lesson 1. Bubble Sort.
  • Lesson 2. Selection Sort.
  • Lesson 3. Insertion Sort.
  • Lesson 4. Merge Sort.
  • Lesson 5. Problems.
    ○ Intersection of 2 sorted arrays
    ○ Union of 2 sorted arrays
    ○ Count Inversions in arrays
  • Lesson 6. Partitions.
    ○ Naive
    ○ Lomuto
    ○ Hoare
  • Lesson 7. Quick Sort.
    ○ Using Lomuto and Hoare
    ○ Time and Space analysis
    ○ Choice of Pivot and Worst case
    ○ Tail call elimination
  • Lesson 8. Problems.
    ○ Kth Smallest element
    ○ Chocolate Distribution Problem
    ○ Sorting arrays with 2 and3 types of elements
    ○ Merge Overlapping Intervals
    ○ Meeting the Maximum Guests
  • Lesson 9. Heap Sort .
  • Lesson 10. Cycle Sort.
  • Lesson 11. Counting Sort.
  • Lesson 12. Radix Sort.
  • Lesson 13. Bucket Sort.
  • Lesson 14. Overview of Sorting Algorithms.

• 8. Matrix

  • Lesson 1. Introduction to Matrix.
  • Lesson 2. Multidimensional Matrix.
  • Lesson 3. Pass Matrix as Argument.
  • Lesson 4. Printing matrix in a snake pattern.
  • Lesson 5. Transposing a matrix.
  • Lesson 6. Check if the element is present in a row and column-wise sorted matrix.
  • Lesson 7. Boundary Traversal.
  • Lesson 8. Spiral Traversal.
  • Lesson 9. Matrix Multiplication.
  • Lesson 10. Search in row-wise and column-wise Sorted Matrix.

• 9. Hashing

  • Lesson 1. Introduction and Time complexity analysis.
  • Lesson 2. Application of Hashing.
  • Lesson 3. Discussion on Direct Address Table.
  • Lesson 4. Working and examples on various Hash Functions.
  • Lesson 5. Introduction and Various techniques on Collision Handling .
  • Lesson 6. Chaining and its implementation.
  • Lesson 7. Open Addressing and its Implementation.
  • Lesson 8. Chaining V/S Open Addressing.
  • Lesson 9. Double Hashing.
  • Lesson 10. C++.
    ○ Unordered Set
    ○ Unordered Map
  • Lesson 11. Java.
    ○ HashSet
    ○ HashMap .
  • Lesson 12. Problems.
    ○ Count Distinct Elements
    ○ Count of the frequency of array elements
    ○ The intersection of two arrays
    ○ Union of two unsorted arrays
    ○ Pair with given sum in an unsorted array
    ○ Subarray with zero-sum
    ○ Subarray with given sum
    ○ Longest subarray with a given sum
    ○ Longest subarray with an equal number of 0’s and 1’s
    ○ Longest common span with the same sum in a binary array
    ○ Longest Consecutive Subsequence
    ○ Count Distinct elements in every window
    ○ More than n/k Occurences
    ○ Optimized More than n/k Solution

• 10. Strings

  • Lesson 1. Discussion of String DS.
  • Lesson 2. Strings in CPP.
  • Lesson 3. Strings in Java.
  • Lesson 4. Problems.
    ○ Given a string, check if they are an anagram of each other.
    ○ Given a string, find the leftmost character that repeats.
    ○ Given a string, find the leftmost character that does not repeat.
    ○ Given a string, find the lexicographic rank of it in O(n) time.
    ○ Implementation of the previously discussed lexicographic rank problem.
    ○ Given a text string and a pattern string, find if a permutation of the pattern exists in the text.
    ○ Given two strings, check if they are rotations of each other or not.
    ○ Various Pattern Searching Algorithms.
    ○ Palindrome Check
  • Lesson 5. Rabin Karp Algorithm.
  • Lesson 6. KMP Algorithm.

• 11. Linked List

  • Lesson 1. Introduction.
  • Lesson 2. Doubly Linked List.
  • Lesson 3. Circular Linked List.
  • Lesson 4. Loop Problems.
    ○ Detecting Loops
    ○ Detecting loops using Floyd cycle detection
    ○ Detecting and Removing Loops in Linked List
  • Lesson 5. Problems.
    ○ Middle of Linked List
    ○ Nth node from the end of linked list
    ○ Deleting a Node without accessing Head pointer of Linked List
    ○ An iterative method to Reverse a linked list
    ○ Recursive method to reverse a linked list
    ○ Reverse in group of size k
    ○ Recursive Traversal in a Singly Linked List
    ○ Segregating even-odd nodes of linked list
    ○ The intersection of two linked list
    ○ Pairwise swap nodes of linked list
    ○ Clone a linked list using a random pointer
    ○ LRU Cache Design
    ○ Merge two Sorted Linked Lists
    ○ Palindrome Linked List
    ○ Recursive Traversal in a Singly Linked List
    ○ Remove Duplicates from a Sorted Singly Linked List
    ○ Sorted Insert in a Singly Linked List
    ○ Reverse a Doubly Linked List
    

• 12. Stack

  • Lesson 1. Understanding the Stack data structure.
  • Lesson 2. Applications of Stack.
  • Lesson 3. Implementation of Stack in Array and Linked List.
  • Lesson 4. Problems.
    ○ Balanced Parenthesis
    ○ Two stacks in an array
    ○ K Stacks in an array
    ○ Stock span problem with variations
    ○ Previous Greater Element
    ○ Next Greater Element
    ○ Largest Rectangular Area in a Histogram
  • Lesson 5. Understanding getMin() in Stack with O(1).
  • Lesson 6. Infix, Prefix and Postfix Introduction.
    ○ Infix to Postfix (Simple Solution)
    ○ Infix to Postfix (Efficient Solution)
    ○ Infix to Prefix (Simple Solution)
    ○ Infix to Prefix (Efficient Solution)
    ○ Evaluation of Prefix

• 13. Queue

  • Lesson 1. Introduction and Application.
  • Lesson 2. Implementation of the queue using array and LinkedList.
  • Lesson 3. SProblems.
    ○ Reversing a Queue
    ○ Generate numbers with given digits
    ○ First Circular Tour

• 14.Deque

  • Lesson 1. Introduction and Application.
  • Lesson 2. Implementation.
  • Lesson 3. Problems.
    ○ Maximums of all subarrays of size k
    ○ ArrayDeque in Java
    ○ Design a DS with min max operations

• 15. Tree

  • Lesson 1. Introduction.
    ○ Tree
    ○ Application
    ○ Binary Tree
    ○ Tree Traversal
  • Lesson 2. Implementation of:
    ○ Inorder Traversal
    ○ Preorder Traversal
    ○ Postorder Traversal
    ○ Level Order Traversal (Line by Line)
    ○ Tree Traversal in Spiral Form
  • Lesson 3. Problems.
    ○ Size of Binary Tree
    ○ Maximum in Binary Tree
    ○ Height of Binary Tree
    ○ Print Nodes at K distance
    ○ Print Left View of Binary Tree
    ○ Children Sum Property
    ○ Check for Balanced Binary Tree
    ○ Maximum Width of Binary Tree
    ○ Convert Binary Tree to Doubly Linked List
    ○ Construct Binary Tree from Inorder and Preorder
    ○ Tree Traversal Spiral Form
    ○ The diameter of a Binary Tree
    ○ LCA problem with an efficient solution
    ○ Burn A Binary Tree from a Leaf
    ○ Count Nodes in a complete Binary Tree
    ○ Serialize and Deserialize a Binary tree
    ○ Iterative Inorder Traversal
    ○ Iterative Preorder Traversal (Simple)
    ○ Iterative Preorder Traversal (Space Optimized)

• 16. Binary Search Tree

  • Lesson 1. Background, Introduction and Application.
  • Lesson 2. Implementation of Search in BST.
  • Lesson 3. Insertion in BST.
  • Lesson 4. Deletion in BST.
  • Lesson 5. Floor in BST.
  • Lesson 6. Self Balancing BST.
  • Lesson 7. AVL Tree.
  • Lesson 8. Red Black Tree.
  • Lesson 9. Set in C++ STL.
  • Lesson 10. Map in C++ STL.
  • Lesson 11. BST Introduction.
  • Lesson 12. TreeSet in java.
  • Lesson 13. TreeMap in Java.
  • Lesson 14. Problems.
    ○ The ceiling of a key in BST
    ○ Ceiling on the left side in an array
    ○ Find Kth Smallest in BST
    ○ Check for BST
    ○ Fix BST with Two Nodes Swapped
    ○ Pair Sum with given BST
    ○ Vertical Sum in a Binary Tree
    ○ Vertical Traversal of Binary Tree
    ○ Top View of Binary Tree
    ○ Bottom View of Binary Tree

• 17. Heap

  • Lesson 1. Introduction & Implementation.
  • Lesson 2. Binary Heap.
    ○ Insertion
    ○ Heapify and Extract
    ○ Decrease Key, Delete and Build Heap
  • Lesson 3. Heap Sort .
  • Lesson 4. Priority Queue.
  • Lesson 5. Problems.
    ○ Sort K-Sorted Array
    ○ Buy Maximum Items with Given Sum
    ○ K Largest Elements
    ○ Merge K Sorted Arrays
    ○ Median of a Stream

• 18. Graph

  • Lesson 1. Introduction to Graph.
  • Lesson 2. Graph Representation.
    ○ Adjacency Matrix
    ○ Adjacency List in CPP and Java
    ○ Adjacency Matrix VS List
  • Lesson 3. Breadth-First Search.
    Applications
  • Lesson 4. Depth First Search.
    Applications
  • Lesson 5. Problems.
    ○ Shortest Path in an Unweighted Graph
    ○ Detecting Cycle
    Topological Sorting
  • Lesson 6. Shortest Path in Directed Acyclic Graph.
  • Lesson 7. Prim's Algorithm/Minimum Spanning Tree.
  • Lesson 8. Dijkstra's Shortest Path Algorithm.
  • Lesson 9. Bellman-Ford Shortest Path Algorithm.
  • Lesson 10. Kruskal’s Algoritm.
  • Lesson 11. Kosaraju's Algorithm.
  • Lesson 12. Articulation Point.
  • Lesson 13. Bridges in Graph.
  • Lesson 14. Tarjan’s Algorithm.
  • Lesson 15. Practice Problems.

• 19. Greedy

  • Lesson 1. Introduction.
  • Lesson 2. Activity Selection Problem.
  • Lesson 3. Fractional Knapsack.
  • Lesson 4. Job Sequencing Problem.
  • Lesson 5. Huffman Coding.

• 20. Backtracking

  • Lesson 1. Concepts of Backtracking.
  • Lesson 2. Rat In a Maze.
  • Lesson 3. N Queen Problem.
  • Lesson 4. Sudoku Problem.

• 21. Dynamic Programming

  • Lesson 1. Introduction.
  • Lesson 2. Dynamic Programming.
    ○ Memoization
    ○ Tabulation
  • Lesson 3. Problems.
    ○ Longest Common Subsequence
    ○ Coin Change Count Combinations
    ○ Edit Distance Problem
    ○ Longest Increasing Subsequence Problem
    ○ Maximum Cuts
    ○ Minimum coins to make a value
    ○ Minimum Jumps to reach at the end
    ○ 0-1 knapsack problem
    ○ Optimal Strategy for a Game
    ○ Variation of Longest Common Subsequence
    ○ Variation of Longest Increasing Subsequence
    ○ Egg Dropping Problem
    ○ Count BST with nkeys
    ○ Maximum Sum with No Consecutive
    ○ Subset Sum Problem
    ○ Matrix Chain Multiplication
    ○ Palindrome Parititioning

• 22. Trie

  • Lesson 1. Introduction.
    ○ Representation
    ○ Search
    ○ Insert
    ○ Delete
  • Lesson 2. Count Distinct Rows in a Binary Matrix.

• 23. Segment Tree

  • Lesson 1. Introduction.
  • Lesson 2. Construction.
  • Lesson 3. Range Query.
  • Lesson 4. Update Query.

• 24. Disjoint Set

  • Lesson 1. Introduction.
  • Lesson 2. Find and Union Operations.
  • Lesson 3. Union by Rank.
  • Lesson 4. Path Compression .
  • Lesson 5. Kruskal's Algorithm.